import java.util.*;

public class Test {
    public int minOperations(int[] nums, int x) {
        int count = Integer.MAX_VALUE;
        int sum = 0;
        int len = nums.length;
        for(int y : nums) {
            sum += y;
        }
        int target = sum - x;

        //数组所有的数据都凑不了 x
        if(target < 0) {
            return -1;
        } else if(target == 0) {
            return len;
        }

        sum = 0;
        for(int left = 0, right = 0; right < len; right++) {
            //进窗口
            sum += nums[right];

            //更新数据
            if(target == sum) {
                count = Math.min(count,len - (right - left + 1));
            }

            //出窗口
            while(sum > target) {
                sum -= nums[left++];
            }

            //更新数据
            if(target == sum) {
                count = Math.min(count,len - (right - left + 1));
            }
        }
        return count == Integer.MAX_VALUE ? -1 : count;
    }

    public int totalFruit(int[] fruits) {
        int baskets = 2;
        int count = Integer.MIN_VALUE;
        Map<Integer,Integer> map = new HashMap<>();
        int len = fruits.length;
        for(int left = 0, right = 0; right < len; right++) {
            int num = fruits[right];

            //进窗口
            map.put(num,map.getOrDefault(num,0) + 1);

            //出窗口
            while(map.size() > 2) {
                int n = fruits[left++];
                map.put(n,map.get(n) - 1);
                if(map.get(n) == 0) {
                    map.remove(n);
                }
            }

            //更新数据
            count = Math.max(count,right - left + 1);
        }
        return count;
    }

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if(p == null || p.length() == 0) {
            return list;
        }
        if(p.length() > s.length()) {
            return list;
        }

        int[] charS = new int[26];
        int[] charP = new int[26];

        int len = p.length();
        int m = len;
        for(int i = 0; i < len; i++) {
            char ch = p.charAt(i);
            charP[ch - 'a']++;
        }
        int count = 0;//记录有效的字母

        len = s.length();
        for(int left = 0, right = 0; right < len; right++) {
            char ch = s.charAt(right);
            if(++charS[ch-'a'] <= charP[ch-'a']) {
                //进窗口
                count++;
            }

            //出窗口
            if(right - left + 1 > m) {
                if(charS[s.charAt(left)-'a']-- <= charP[s.charAt(left)-'a']) {
                    count--;
                }
                left++;
            }

            //更新数据
            if(count == m) {
                list.add(left);
            }
        }

        return list;
    }

    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
        int len = words[0].length();
        Map<String,Integer> map = new HashMap<>();
        for(String str : words) {
            map.put(str,map.getOrDefault(str,0) + 1);
        }

        int length = s.length();
        int count = 0;//记录有效数据个数
        int size = words.length;//记录数组的元素总数
        Map<String,Integer> mapS = new HashMap<>();
        for(int left = 0, right = len; right < length;) {
            String str = s.substring(right - len,right);
            //进窗口
            if(map.containsKey(str)) {
                mapS.put(str, mapS.getOrDefault(str,0) + 1);
                if(map.get(str) >= mapS.get(str)) {
                    count++;
                } else {
                    //去重
                    while(s.substring(left,left + len) != str) {
                        remove(mapS, len, left, s);
                        left += len;
                        count--;
                    }
                    count++;
                }
                right += len;
            }

            //出窗口
            if(!map.containsKey(str)) {
                left = right - len + 1;
                right++;
                count = 0;
                mapS.clear();
            }

            //更新数据
            if(count == size) {
                list.add(left);
                remove(mapS,len,left,s);
                left += len;
                count--;
            }
        }
        return list;
    }

    private static void remove(Map<String,Integer> map, int len, int left, String s) {
        String ss = s.substring(left,left + len);
        map.put(ss,map.get(ss) - 1);
        if(map.get(ss) == 0) {
            map.remove(ss);
        }
    }

    public static void main(String[] args) {
        /*int[] nums = {5207,5594,477,6938,8010,7606,2356,6349,3970,751
                ,5997,6114,9903,3859,6900,7722,2378,1996,8902,228,
                4461,90,7321,7893,4879,9987,1146,8177,1073,7254,5088,
                402,4266,6443,3084,1403,5357,2565,3470,3639,9468,8932,
                3119,5839,8008,2712,2735,825,4236,3703,2711,530,9630,1521,
                2174,5027,4833,3483,445,8300,3194,8784,279,3097,1491,9864,
                4992,6164,2043,5364,9192,9649,9944,7230,7224,585,3722,5628,
                4833,8379,3967,5649,2554,5828,4331,3547,7847,5433,3394,4968,
                9983,3540,9224,6216,9665,8070,31,3555,4198,2626,9553,9724,4503,
                1951,9980,3975,6025,8928,2952,911,3674,6620,3745,6548,4985,5206,
                5777,1908,6029,2322,2626,2188,5639};*/
        //System.out.println(minOperations(nums, 565610));

        int[] nums = {1,2,3,2,2};
        int[] nums2 = {1,2,3,2,2};
        Arrays.equals(nums,nums2);

        String s = "barfoothefoobarman";
        String[] words = {"foo","bar"};
        findSubstring(s,words);

    }
}
